package com.leetcode.贪心;

/**
 * 给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
 * （当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
 * @author LZF
 *
 */
public class L738单调递增的数字 {
	public static void main(String[] args) {
		System.out.println(monotoneIncreasingDigits(1234));
	}
	/**
	 * 例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增）
	 * 首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。
	 * 这一点如果想清楚了，这道题就好办了。
	 * 局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]--，然后strNum[i]给为9，
	 * 可以保证这两位变成最大单调递增整数
	 * 全局最优：得到小于等于N的最大单调递增的整数。
	 * 
	 * 通过推到可以看到，很明显应该从后开始往前遍历，因为
	 * 从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，
	 * 让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。
	 * 这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。
	 */
	public static int monotoneIncreasingDigits(int n) {
		char[] num = Integer.toString(n).toCharArray();
		// flag用来标记赋值9从哪里开始
        // 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
		int flag = num.length;
		for(int i = num.length - 1;i > 0;i--) {
			if(num[i - 1] > num[i]) {
				flag = i;
				num[i - 1]--;
			}
		}
		for(int i = flag;i < num.length;i++) {
			num[i] = '9';
		}
		return Integer.parseInt(new String(num));
    }
}
